package arrayandstring;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * https://leetcode-cn.com/problems/find-target-indices-after-sorting-array/
 */
public class E2089_FindTargetIndicesAfterSortingArray {
    /**
     * 官方解法
     * 时间复杂度 O(nlogn) 空间复杂度 O(n) 
     */
    public List<Integer> targetIndices(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums); // O(nlogn)
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == target) list.add(i);
        }
        return list;
    }
    /**
     * (推荐)官方解法
     * 时间复杂度 O(n) 空间复杂度 O(1) 
     * 不需要排序
     * 统计nums[x] < target 和 nums[x] == target 的个数 m 和 n
     * 符合要求的下标是区间 [m, m+n) 的所有整数
     */
    public List<Integer> targetIndices1(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        int m = 0, n = 0;
        for (int i = 0; i < nums.length; ++i) {
           if (nums[i] < target)  m++;
           if (nums[i] == target) n++;
        }
        for (int j = m; j < m+n; j++) list.add(j);
        return list;
    }
    /**
     * (不推荐)
     * 时间复杂度 O(n*n) 空间复杂度 O(n) 
     */
    public List<Integer> targetIndices2(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        // 整个排序[doge]
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i+1; j < nums.length; ++j) {
                if (nums[i] > nums[j]) {
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        // 开找target[doge]
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == target) {
                list.add(i);
            }
        }
        return list;
    }
}
